#include <iostream>
#include <map>
#include <fstream>
#include <ctime>
#include <unistd.h>
#include <cstdlib>
#include <vector>
#include <ctype.h>
#include <cmath>
#include <omp.h>
#include <algorithm>
#include "mpi.h"

using namespace std;

//struct utilizada nos vetores
//composta pela palavra (st) e número de ocorrências (occurrences)
typedef struct word
{
    string st;
    int occurrences;
};

//Função que tenta encontrar a palavra passada por parâmetro, decompondo
//até, no máximo, um caracter
int process_words(string st, map<string,int*> *map_words)
{
	map<string,int*>::iterator it;
	it = map_words->find(st);
	if(it != map_words->end())
		return 1;
	
	int middle = st.size()/2;
	int lpos = middle;
	string lst = st.substr(0, lpos);
	string rst = st.substr(lpos, string::npos);
	
	while(lpos > 0)
	{
		//Tenta encontrar o lado esquerdo da palavra
		if(lst.size() > 0)
		{
			it = map_words->find(lst);
			if(it != map_words->end())
				lst.clear();
			else
				lpos--;
		}
		
		//Tenta encontrar o lado direito da palavra
		if(rst.size() > 0)
		{
			it = map_words->find(rst);
			if(it != map_words->end())
				rst.clear();
		}
		
		//Se encontrou as duas partes, retorna 1
		if(lst.size() == 0 && rst.size() == 0)
			return 1;
		//Senao, continua processando
		else
		{
			if(rst.size() > 0)
				rst = st.substr(lpos, string::npos);
			if(lst.size() > 0)
				lst = st.substr(0, lpos);
			else
				break;
			
		}
	}
	//Se não encontrou nem a primeira letra do lado esquerdo, para execucao
	if(lpos == 0)
		return 0;
	
	int rpos;
	if(rst.size() > 0)
	{
		rpos = middle+1;
		//Se a execucao nao parou, explora o lado direito
		while(rpos < st.size())
		{
			rst = st.substr(rpos, string::npos);
			
			it = map_words->find(rst);
			if(it != map_words->end())
				rst.clear();
			else
				rpos++;
			
			if(rst.size() == 0)
				break;
		}
	}
	else
		rpos = lpos;
	
	//Se não restou caracteres, não pode encontrar - retorna 0
	if(rpos == st.size()-1)
		return 0;
	
	//Substring restante a ser procurada
	st = st.substr(lpos, (rpos-lpos));
	//Se é nula, quer dizer que todos segmentos foram encontrados - retorna 1
	if(st.size() == 0)
		return 1;
	
	//Recursivamente, tenta resolver novamente o restante da string
	return process_words(st, map_words);
}

//Função para ler um mapa do arquivo,
//inserindo o conteúdo no mapa passado por referência
void read_map(map<string,int*> *m, const char *fname)
{
	ifstream f;
	f.open(fname);
	while(f.good())
	{
		string st;
		f >> st;
		if(st.size() > 0)
		{
			int *vn = (int*)malloc(3*sizeof(int));
			f >> vn[0];
			f >> vn[1];
			f >> vn[2];
			m->insert(pair<string,int*>(st, vn));
		}
	}
}

//Função para ler um vetor de prefixos ou sufixos,
//copiando o conteúdo para o vector passado como referência
void read_pref_suf(vector<word*> *v, const char *fname)
{
	ifstream f;
	f.open(fname);
	while(f.good())
	{
		string st;
		f >> st;
		if(st.size() > 0)
		{
			word *new_word = new word();
			new_word->st = st;
			f >> new_word->occurrences;
			v->push_back(new_word);
		}
	}
}

//Função que gera palavras aleatórias
string generate_word(int size)
{
	string str;
	//#pragma omp parallel for
	for(int i = 0; i < size; i++)
	{
		int r = lrand48()%26;
		r+= 65;
		str += ((char) r);
	}
	
	return str;
}


int main(int argc, char *argv[])
{
	//tempo inicial
	clock_t time1, time2, time_diff;
	time1 = clock()/(CLOCKS_PER_SEC/1000);

	int numtasks, rank, rc, dest, source, count, tag=1;
	MPI_Status Stat;
	int Nodes,i;

	long int seed;	
	seed = 123456789L;
	srand48(seed);

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &Nodes);


	if(rank == 0)
	{
	
		//tá faltando o vetor de tamanhos
		int size_of_words[] = {24, 196, 847, 2592, 4438, 6893, 8611, 9615, 
			9552, 8266, 6489, 4512, 3009, 1817, 999, 570, 319, 117, 49, 22, 
			14, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
			0, 0, 0, 1};
		
		int found = 0;
	
		map<string,int*> map_words;
		//leitura do mapa
		read_map(&map_words, "map");
		
		//Geração de palavras aleatorias de 1 ate 5 letras
		//Para cada posicao do vetor, resolve todas as palavras
		int i =0;
        int source;
		//#pragma omp parallel for reduction(+:found)
		while(1)
		{
			//cout << i << endl;
			if(i == 5)
			{
				i = -1;
				for(source = 2;source < Nodes; source++)
				rc = MPI_Send(&i, 1, MPI_INT, source, tag, MPI_COMM_WORLD);
				break;
			}			
			else
			{
                char wordr[5][6];
                //no. de palavras daquela posicao do vetor
                int n_words = size_of_words[i];
                //cout << "Ciclo de " << i+1 << " letra(s):" << endl;
                //enquanto houver palavras,
                #pragma omp shared(n_words) schedule(dynamic) reduction(-:n_words)
                while(n_words > 0)
                {
                    for(source=2; source < Nodes; source++)
                    {
                        MPI_Send(&i, 1, MPI_INT, source, tag, MPI_COMM_WORLD);
                        //wordr[source-1] = (char*)realloc(wordr[source-1],(i+1)*sizeof(char));						
                        MPI_Recv(wordr[source-1], 6, MPI_CHAR, source, tag, MPI_COMM_WORLD, &Stat);
						//cout << "no" << source << " gerou palavra" << wordr[source-1] << endl;
                    }

                    //#pragma omp parallel for reduction(+:found)
                    for(int source=1; source < Nodes; source++)
                    {
                        //tenta encontrar a palavra no mapa pelo iterador it
                        map<string,int*>::iterator it_w = map_words.find(wordr[source-1]);
                        //Se encontrar,
                        if(it_w != map_words.end())
                        {
                            //e se a palavra ainda nao foi encontrada,
                            if(it_w->second[0] == 0)
                            {
                                //incrementa o valor de entrada
                                it_w->second[0]++;
                                //reduz o numero de palavras a encontrar
                                n_words--;
                                //incrementa o no. de paalvras encontradas
                                found++;
                            }
                        }
                    }
                }
            }
            i++;
		}
            
		cout << "Primeiras: found = " << found << endl;
		
		//receber palavras geradas pelo nó 1
		int found1;
		MPI_Recv(&found1,1,MPI_INT, 1, tag, MPI_COMM_WORLD, &Stat);
		//rc = MPI_Recv(&k, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &Stat);		

		//Contabiliza as palavras recebidas
		found += found1;
		
		cout << "Primeiras + sufixo = " << found << endl;

		time2 = clock()/(CLOCKS_PER_SEC/1000);
		time_diff = time2 - time1;
		cout << "tempo de execucao " << time_diff << " ms";
		
	}
	else if(rank == 1)
	{
		int found = 0;
		map<string,int*> map_words;
		//leitura do mapa
		read_map(&map_words, "map");
		
		//leitura de prefixos
		vector<word*> prefixes;
		read_pref_suf(&prefixes, "prefix");

		//Geração de palavras por combinação de prefixo + 1 ou mais palavras
		//Gera uma combinação de um prefixo + uma ou mais palavras
		for(int i = 0; i < prefixes.size(); i++)
		{
			//pega o sufixo
			string pref = prefixes.at(i)->st;
			//procura, pelo iterador, as palavras que começam com ele
			map<string,int*>::iterator it_p = map_words.upper_bound(pref);
			//avança aquelas que já foram encontradas
			while(it_p->second[0] == 1)
				it_p++;

			//Se ainda há ocorrências deste sufixo
			while(prefixes.at(i)->occurrences > 0)
			{
				//pula palavras que tenham 5 letras ou menos
				while(it_p->first.size() <= 5)
					it_p++;
				
				//Se o prefixo mudou, encerra o laço (palavra nao sera encontrada)
				if(it_p->first.substr(0,pref.size()) != pref)
					break;
				//pega a palavra a ser encontrada
				string st = it_p->first;
				//remove o prefixo
				st = st.substr(pref.size(), string::npos);
				//processa a palavra, tentando decompo-la e achar cada cada parte,
				//formando a palavra completa
				if(process_words(st, &map_words) == 1)
				{
					if(it_p->second[0] == 0)
					{
						it_p->second[0]++;
						prefixes.at(i)->occurrences--;
						found++;
					}
				}
				
				//encontrando a palavra ou nao, avanca o iterador para a proxima palavra
				it_p++;
				//se o iterador estorou a capacidade do map, para a execucao
				if(it_p == map_words.end())
					break;
			}
		}
		//cout << "found = " << found << endl;
		
		MPI_Send(&found, 1, MPI_INT, 0,  tag, MPI_COMM_WORLD);	
		//rc = MPI_Send(word, 6, MPI_CHAR, 0, tag, MPI_COMM_WORLD);			
	
	}
	
	else  // nos com rank maior que 1 geram palavras e passam para o rank 0 procurar no mapa
	{
        char *word;
		int k;

		rc = MPI_Recv(&k, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &Stat);
		while(1)
		{
			if(k == -1)
				break;
			string aux = generate_word(k+1);
			word = new char[6];
			strcpy(word, aux.c_str());			
			strcat(word, "\0");
			rc = MPI_Send(word, 6, MPI_CHAR, 0, tag, MPI_COMM_WORLD);			
			rc = MPI_Recv(&k, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &Stat);

		}	

	}


	MPI_Finalize();

	
	
	
	return 0;

}
